package 中等.拓扑排序;

import java.util.*;

/**
 * 给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。
 * 还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
 * 检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且
 * 所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存
 * 在多个有效的 超序列 。
 * 例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
 * 而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。
 * [1,2,3,4] 是可能的超序列，但不是最短的。
 * 如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。
 * 子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/ur2n8P
 */
public class 重建序列_offer115 {

    public static void main(String[] args) {

        int[] nums = {1, 2, 3};
        int[][] sequences = {{1, 2}, {1, 3}, {2, 3}};
        System.out.println(sequenceReconstruction(nums, sequences));

    }

    /**
     * 拓扑排序
     * 因为 nums 是范围为 [1，n] ，直接用一个数组记录每个数字的入度
     * 拓扑排序的思路:
     * 去掉入度为 0 的节点，会出现新的入度为 0 的节点
     * 即为下一层的节点
     *
     * @param nums
     * @param sequences
     * @return
     */
    public static boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int[] degree = new int[nums.length + 1];
        // 当前节点指向的下一个节点集合
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 1; i <= nums.length; i++) {
            map.put(i, new HashSet<>());
        }

        for (int[] sequence : sequences) {
            for (int i = 1; i < sequence.length; i++) {
                degree[sequence[i]]++;
                map.get(sequence[i - 1]).add(sequence[i]);
            }
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i < degree.length; i++) {
            if (degree[i] == 0) {
                queue.addLast(i);
            }
        }

        int index = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            if (size > 1) return false;
            while (size-- > 0) {
                int num = queue.pollFirst();
                if (nums[index] != num) return false;
                degree[num]--;
                for (Integer nextNum : map.get(num)) {
                    degree[nextNum]--;
                    // 只有下一层有可能入度变成 0
                    if (degree[nextNum] == 0) {
                        queue.addLast(nextNum);
                    }
                }
                index++;
            }
        }
        return true;
    }

}
